package offer;

import java.util.*;

/**
 * Creared with IntelliJ IDEA.
 * Description:给定一棵结点数为n 二叉搜索树，请找出其中的第 k 小的TreeNode结点值。
 * 1.返回第k小的节点值即可
 * 2.不能查找的情况，如二叉树为空，则返回-1，或者k大于n等等，也返回-1
 * 3.保证n个节点的值不一样
 * User:yxd
 * Date:2022-07-09
 * Time:22:53
 */
public class JZ54 {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param proot TreeNode类
     * @param k int整型
     * @return int整型
     */

    static class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
        public TreeNode(int val) {
            this.val = val;
        }
    }
    public ArrayList<Integer> list = new ArrayList<>();
    public int KthNode (TreeNode proot, int k) {
        // write code here
        if(proot == null)return -1;
        inorder(proot);
        if(k < 0 || k > list.size()){
            return -1;
        }
        return list.get(k - 1);
    }
    public void inorder(TreeNode root){
        if(root == null)return;
        inorder(root.left);
        list.add(root.val);
        inorder(root.right);

    }
//    用栈记录当前节点，不断往左深入，直到左边子树为空。
//    再弹出栈顶（即为当前子树的父节点），访问该节点，同时计数。
//    然后再访问其右子树，其中每棵子树都遵循左中右的次序。
//    直到第k个节点返回，如果遍历结束也没找到，则返回-1.
    public int KthNode1 (TreeNode proot, int k) {
        if(proot == null || k <= 0)return -1;
        Stack<TreeNode> stack = new Stack<>();
        int count = 0;
        TreeNode cur = null;
        while(!stack.isEmpty() || proot != null){
            while(proot != null){
                stack.push(proot);
                //一直向左遍历，直到左树为空，再看右树
                proot = proot.left;
            }
            cur = stack.pop();
            count ++;
            if(count == k){
                return cur.val;
            }
            proot = cur.right;
        }
        return -1;
    }
}
